package com.study;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.*;

public class BinarySearch
{
    // 递归版本
    private static int f(int[] a, int target, int i, int j) {
        if (i > j) {
            return -1;
        }

        int m = (i + j) >>> 1;
        if (target < a[m]) {
            return f(a, target, i, m - 1);
        } else if (a[m] < target) {
            return f(a, target, m + 1, j);
        } else {
            return m;
        }
    }

    // 返回值是 <= 目标的最靠 右 的索引
    public int binarySearchRightmost2(int[] a, int target)
    {
        int i = 0, j = a.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (target >= a[m]) {
                // 目标在右侧或者已经找到目标，移动左边界
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i - 1;
    }

    // 返回值是大于等于目标的最靠左的索引
    public int binarySearchLeftmost2(int[] a, int target)
    {
        int i = 0, j = a.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (target <= a[m]) {
                // 目标在左侧或者已经找到目标，移动右边界
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    public int binarySearchLeftmost1(int[] a, int target)
    {
        int i = 0, j = a.length - 1;
        int candicate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candicate = m;
                // leftmost 是移动右边界， rightmost 则是移动左边界
                j = m - 1;
            }
        }
        return candicate;
    }

    @Test
    @DisplayName("测试 binarySearchLeftmost 返回 -1")
    public void test6()
    {
        int[] a = {1, 2, 4, 4, 4, 5, 6, 7};
        assertEquals(0, binarySearchLeftmost1(a, 1));
        assertEquals(1, binarySearchLeftmost1(a, 2));
        assertEquals(2, binarySearchLeftmost1(a, 4));
        assertEquals(5, binarySearchLeftmost1(a, 5));
        assertEquals(6, binarySearchLeftmost1(a, 6));
        assertEquals(7, binarySearchLeftmost1(a, 7));

        assertEquals(-1, binarySearchLeftmost1(a, 0));
        assertEquals(-1, binarySearchLeftmost1(a, 3));
        assertEquals(-1, binarySearchLeftmost1(a, 8));
    }

    @Test
    @DisplayName("测试 binarySearch java 版")
    public void test5()
    {
        int[] a = {2, 5, 8};
        int target = 4;
        int result = Arrays.binarySearch(a, target);
        assertEquals(-2, result);

        int insertion = -(result + 1);
        int[] b = new int[a.length + 1];
        System.arraycopy(a, 0, b, 0, insertion);
        b[insertion] = target;
        System.arraycopy(a, insertion, b, insertion + 1, a.length - insertion);

        assertArrayEquals(new int[]{2, 4, 5, 8}, b);
    }

    // 平衡版：三分支改成两分支，当范围内只有一个元素时，就退出循环，在循环外进行比较
    public int binarySearchBalance(int[] a, int target)
    {
        int i = 0, j = a.length;
        while (j - i > 1) {         // 范围内还有多个元素则继续移动边界缩小范围，j-i == 1 时，就剩下 i 索引的值
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        return (target == a[i]) ? i : -1;
    }

    @Test
    @DisplayName("测试 binarySearchBalance")
    public void test4()
    {
        int[] a = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(0, binarySearchBalance(a, 7));
        assertEquals(1, binarySearchBalance(a, 13));
        assertEquals(2, binarySearchBalance(a, 21));
        assertEquals(3, binarySearchBalance(a, 30));
        assertEquals(4, binarySearchBalance(a, 38));
        assertEquals(5, binarySearchBalance(a, 44));
        assertEquals(6, binarySearchBalance(a, 52));
        assertEquals(7, binarySearchBalance(a, 53));

        assertEquals(-1, binarySearchBalance(a, 0));
        assertEquals(-1, binarySearchBalance(a, 15));
        assertEquals(-1, binarySearchBalance(a, 60));
    }

    // 改动版：j 不参与比较，只作为边界
    public int binarySearchAlternative(int[] a, int target)
    {
        int i = 0, j = a.length;    // 1、定义边界
        while (i < j) {             // 3、结束条件
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;              // 2、右边界移动的位置
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    @Test
    @DisplayName("测试 binarySearchAlternative ")
    public void test3()
    {
        int[] a = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(0, binarySearchAlternative(a, 7));
        assertEquals(1, binarySearchAlternative(a, 13));
        assertEquals(2, binarySearchAlternative(a, 21));
        assertEquals(3, binarySearchAlternative(a, 30));
        assertEquals(4, binarySearchAlternative(a, 38));
        assertEquals(5, binarySearchAlternative(a, 44));
        assertEquals(6, binarySearchAlternative(a, 52));
        assertEquals(7, binarySearchAlternative(a, 53));

        assertEquals(-1, binarySearchAlternative(a, 0));
        assertEquals(-1, binarySearchAlternative(a, 15));
        assertEquals(-1, binarySearchAlternative(a, 60));
    }

    public int binarySearchBasic(int[] a, int target)
    {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    @Test
    @DisplayName("测试 binarySearchBasic")
    void test1()
    {
        int[] a = {7, 13, 21, 30, 38, 44, 52, 53};
        assertEquals(0, binarySearchBasic(a, 7));
        assertEquals(1, binarySearchBasic(a, 13));
        assertEquals(2, binarySearchBasic(a, 21));
        assertEquals(3, binarySearchBasic(a, 30));
        assertEquals(4, binarySearchBasic(a, 38));
        assertEquals(5, binarySearchBasic(a, 44));
        assertEquals(6, binarySearchBasic(a, 52));
        assertEquals(7, binarySearchBasic(a, 53));

        assertEquals(-1, binarySearchBasic(a, 0));
        assertEquals(-1, binarySearchBasic(a, 15));
        assertEquals(-1, binarySearchBasic(a, 60));
    }
}
